package Sort;

import java.util.Random;
import java.util.concurrent.ThreadLocalRandom;
/**
 * 七大排序
 * @author lumin
 * @date 2022/03/16 13:44
 **/

public class
SevenSort {
    private static final ThreadLocalRandom random = ThreadLocalRandom.current();

    /**
     * 单项选择排序
     * @param arr
     */
    public static void selectionSort(int[] arr){
        for (int i = 0; i < arr.length - 1; i++) {
            //min为当前最小值的索引
            int min = i;
            for (int j = i; j < arr.length; j++) {
                if(arr[j] < arr[min]){
                    min = j;
                }
            }
            swap(arr,min,i);
        }
    }

    /**
     *双向选择排序
     * @param arr
     */
    public static void selectionSortOP(int[] arr){
        int low = 0;
        int hight = arr.length - 1;
        while(low <= hight){
            int max = low;
            int min = low;
            for (int i = low; i <= hight; i++) {
                if(arr[i] > arr[max]){
                    max = i;
                }
                if(arr[i] < arr[min]){
                    min = i;
                }
            }
            swap(arr,low,min);
            if(max == low){
                //最大值已经被换到min
                max = min;
            }
            swap(arr,max,hight);
            low++;
            hight--;
        }
    }

    /**
     * 希尔排序
     * @param arr
     */
    public static void shellSort(int[] arr){
        int gap = arr.length >> 1;
        while(gap > 1){
            inSertionSortByGap(arr,gap);
            gap = gap >> 1;
        }
        inSertionSort(arr);
    }

    /**
     * 按gap分组进行插入排序
     * @param arr
     * @param gap
     */
    private static void inSertionSortByGap(int[] arr,int gap) {
        for (int i = gap; i < arr.length; i++) {
            //不断向前看gap位置的元素
            for (int j = i; j - gap >= 0 && arr[j] < arr[j - gap]; j -= gap) {
                swap(arr,j,j - gap);
            }
        }
    }

    /**
     * 归并排序
     * @param arr
     */
    public static void mergeSort(int[] arr){
        mergeSortInternal(arr,0,arr.length - 1);
    }

    /**
     * 归并排序非递归写法
     * @param arr
     */
    public static void mergeSortNoRecursion(int[] arr){
        for (int sz = 1; sz <= arr.length; sz += sz) {
            for (int i = 0; i + sz< arr.length; i += 2 * sz) {
                merge(arr,0,i + sz - 1,Math.min(i + 2 * sz - 1,arr.length - 1));
            }
        }
    }

    /**
     * 拆分原数组,直至每个小数组只有一个元素
     * @param arr
     * @param l
     * @param r
     */
    private static void mergeSortInternal(int[] arr, int l, int r) {
        //区间小于15直接进行插入排序
        if(r - l <= 15){
            inSertionSort(arr);
            return;
        }
        if(l >= r){
            return;
        }
        int mid = l + ((r - l) >> 1);
        //继续拆分左右两个小数组
        mergeSortInternal(arr,l,mid);
        mergeSortInternal(arr,mid + 1,r);
        //拆分结束,开始合并
        if(arr[mid] > arr[mid + 1]){
            merge(arr,l,mid,r);
        }
    }

    /**
     * 合并拆分后的小数组,一次合并两个
     * arr[l,mid]   arr[mid + 1,r]
     * 合并后的数组arr[l,r]
     * @param arr
     * @param l
     * @param mid
     * @param r
     */
    private static void merge(int[] arr, int l, int mid, int r) {
        //先创建一个新的临时数组aux
        int[] aux = new int[r - l + 1];
        //将arr中的元素复制到aux中
        for (int i = 0; i < aux.length; i++) {
            aux[i] = arr[i + l];
        }
        //i为左侧小数组开始的索引
        int i = l;
        //j为右侧大区间开始的索引
        int j = mid + 1;
        for (int k = l; k <= r; k++) {
            if(i > mid){
                arr[k] = aux[j - l];
                j++;
            }else if(j > r){
                arr[k] = aux[i - l];
                i++;
            }else if(aux[i - l] > arr[j - l]){
                arr[k] = aux[j - l];
                j++;
            }else{
                arr[k] = aux[i - l];
                i++;
            }
        }
    }

    /**
     * 快速排序
     * @param arr
     */
    public static void quickSort(int[] arr){
        quickSortInternal(arr,0,arr.length - 1);
    }

    /**
     * 在[l ... r]上进行快速排序
     * @param arr
     * @param l
     * @param r
     */
    private static void quickSortInternal(int[] arr, int l, int r) {
        if(r - l <= 15){
            inSertionSort(arr);
            return;
        }
        //获取分区点
        int p = partition(arr,l,r);
        //在左右区间上重复进行快速排序
        quickSortInternal(arr,l,p - 1);
        quickSortInternal(arr,p + 1,r);
    }

    private static int partition(int[] arr, int l, int r) {
        // 随机在当前数组中选一个数作为基准值
        int randomIndex = random.nextInt(l,r);
        swap(arr,l,randomIndex);
        int v = arr[l];
        int j = l;
        for (int i = l + 1; i <= r; i++) {
            if(arr[i] < v){
                swap(arr,j + 1,i);
                j++;
            }
        }
        swap(arr,l,j);
        return j;
    }

    /**
     * 直接插入排序
     * @param arr
     */
    public static void inSertionSort(int[] arr){
        //已排序区间[0,i);
        //未排序区间[i,n);
        for (int i = 0; i < arr.length; i++) {
            //待排序区间的第一个元素arr[i]
            //从待排序区间的第一个元素向前看,找到合适的插入位置
//            for (int j = i; j > 0; j--) {
//                //当arr[j]>arr[j - 1]的时候,说明当前元素大于已排序区间的最大值
//                if(arr[j] >= arr[j - 1]){
//                    //"="也不交换,保证稳定性
//                    break;
//                }else {
//                    swap(arr,j,j - 1);
//                }
//            }
            for (int j = i; j - 1 >= 0 && arr[j] < arr[j - 1]; j--) {
                swap(arr,j,j - 1);
            }
        }
    }


    /**
     * 冒泡排序
     * @param arr
     */
    public static void bubbleSort(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if(arr[j] > arr[j + 1]){
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }




    /**
     * @author lumin
     * @date 2022/03/16 13:02
     **/
    public static void swap(int[] arr,int i ,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}